package leetcode_2401_2500;

public class LeeCode_2407 {
    public static void main(String[] args) {

    }
    private static int lengthOfLIS(int[] nums, int k) {
        int u = 0;
        for (int x : nums) {
            u  =Math.max(u, x);
        }
        int[] max = new int[u * 4];
        for (int x : nums) {
            if (x == 1){
                modify(max, 1, 1, u, 1, 1);
            }else {
                int res = query(max, 1, 1, u, Math.max(x - k, 1), x - 1) + 1;
                modify(max, 1, 1, u, x, res);
            }
        }
        return max[1];
    }
    private static void modify(int[] max, int o, int l, int r, int idx, int val){
        if (l == r){
            max[o] = val;
            return;
        }
        int m = (l + r) >> 1;
        if (idx <= m){
            modify(max, o * 2, l, m, idx, val);
        }else {
            modify(max, o * 2 + 1, m + 1, r, idx, val);
        }
        max[o] = Math.max(max[o * 2], max[o * 2 + 1]);
    }
    private static int query(int[] max, int o, int l, int r, int L, int R){
        if (L <= l && r <= R){
            return max[o];
        }
        int m = (l + r) >> 1, res = 0;
        if (L <= m){
            res = query(max, o * 2, l, m, L, R);
        }
        if (R > m){
            res = Math.max(res, query(max, o * 2 + 1, m + 1, r, L, R));
        }
        return res;
    }
}